#include<vector>
#include<algorithm>
#include<iostream>
using std::min;
using std::vector;


class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int dp[m][n];
        // 遍历边界
        dp[0][0] = grid[m-1][n-1];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[m-i-1][n-1];
            //std::cout << dp[i][0] << "\n";
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[m-1][n-j-1];
            //std::cout << dp[0][j] << "\n";
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j ++) {
                dp[i][j] = grid[m-i-1][n-j-1] + min(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }
};

int main() {
    vector<vector<int>> grid = {{1, 2, 3}, {4, 5, 6}};
    std::cout << Solution().minPathSum(grid) << "\n";
}